{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 极大似然"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "极大似然（Maximum Likelihood）估计为用于已知模型的**参数估计**的统计学方法。\n",
    "\n",
    "也就是求使得似然函数最大的代估参数的值。而**似然函数就是如果参数已知则已出现样本出现的概率**。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "比如，我们想了解抛硬币是正面（head）的概率分布$θ$；那么可以通过最大似然估计方法求得：\n",
    "\n",
    "$$\\hat{θ} =argmax_x l(θ)=argmax_x θ^8 (1−θ)^2  $$\n",
    "\n",
    "其中，$l(θ)$为观测变量序列的似然函数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "所以最大似然方法估计参数，就是先假设参数已知，然后用参数，求出样本出现的概率。如果是多个样本，就是多个样本的联合概率最大"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "求解使似然函数最大的代估参数，常规的做法就是对似然函数求导，求使导数为0的自变量的值，以及左右边界线的值。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "例如：\n",
    "\n",
    "对$l(θ)$求偏导\n",
    "\n",
    "$$\\frac{∂l(θ)}{∂θ} =θ^7 (1−θ)(8−10θ)⇒\\hat{θ} =0.8 $$\n",
    "\n",
    "但是如果似然函数不是凹函数（concave），求解极大值困难。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一般地，使用与之具有相同单调性的log-likelihood，如图所示也就是将似然函数求log。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![这里写图片描述](https://img-blog.csdnimg.cn/img_convert/1e6d67345af90c1dc688cbdeb987f65b.png)\n",
    "\n",
    "所谓的凹函数和凸函数，凹函数斜率逐渐减小，凸函数斜率逐渐增大。\n",
    "\n",
    "所以凹函数“容易”求解极大值（极值为0时），凸函数“容易”求解极小值（极值为0时）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# EM算法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "EM算法（Expectation Maximization）是在含有隐变量（latent variable）的模型下计算最大似然的一种算法。\n",
    "\n",
    "所谓隐变量，是指**我们没有办法观测到的变量。**\n",
    "\n",
    "比如，有两枚硬币A、B，每一次随机取一枚进行抛掷，我们只能观测到硬币的正面与反面，而不能观测到每一次取的硬币是否为A；则称每一次的选择抛掷硬币为隐变量。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "用Y表示观测数据，Z表示隐变量；\n",
    "\n",
    "Y和Z连在一起称为完全数据( complete-data )，观测数据Y又称为不完全数据(incomplete-data)。\n",
    "\n",
    "观测数据的似然函数：\n",
    "$$P(Y|θ)=∑ _z P(Z|θ)P(Y|Z,θ) $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "求模型参数的极大似然估计：\n",
    "\n",
    "$$\\hat{θ}  =argmax_{θ} logP(Y|θ) $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "因为含有隐变量，此问题无法求解。因此，Dempster等人提出EM算法用于迭代求解近似解。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "所以EM算法是一种特殊情况下的最大似然求解方法。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "EM算法比较简单，分为两个步骤："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " - E步（E-step），以当前参数$θ^{(i)}$ 计算$Z$的期望值。因为期望值中不再包含未知的隐含变量Z，所以是可以计算的。\n",
    "\n",
    "$$Q(θ,θ^{(i)} )=E_Z [logP(Y,X|θ)|Y,θ^{(i)} ] $$\n",
    "\n",
    " - M步（M-step），求使$Q(θ,θ^{(i)})$极大化的$θ$，确定第$i+1$次迭代的参数的估计值$θ^{(i+1)}$\n",
    "\n",
    "$$θ^{(i+1)} =argmax_θ   Q(θ,θ^{(i)} ) $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如此迭代直至算法收敛。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 案例"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如图所示，有两枚硬币A、B，每一个实验随机取一枚抛掷10次，共5个实验，我们可以观测到每一次所取的硬币，估计参数A、B为正面的概率$θ=(θ_A ,θ_B )$ ，根据极大似然估计求解。\n",
    "\n",
    "![这里写图片描述](https://img-blog.csdnimg.cn/img_convert/d23a17394f0c6e97e1a83b30bfacdf60.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果我们不能观测到每一次所取的硬币，只能用EM算法估计模型参数，算法流程如图所示：\n",
    "\n",
    "![这里写图片描述](https://img-blog.csdnimg.cn/img_convert/aa3a1eebe2cd32ca3d3cf608410f9531.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "隐变量$Z$为每次实验中选择A或B的概率，并初始化A为正面的概率为0.6，B为正面的概率为0.5。\n",
    "\n",
    "实验进行了5次。每次都要进行一遍EM操作。每次都要计算隐含变量。取A的概率，和取B的概率。\n",
    "\n",
    "然后更新代估参数$θ_A$（A为正面的概率）和$θ_B$（B为正面的概率）的值。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在初始化$θ_A=0.6$和$θ_B=0.5$后第一次实验后计算隐含变量（选择A的概率）为"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$P(z_1 =A|y_1 ,θ^0)=\\frac{z_1为A的话，样本结果出现的概率}{z_1为任何可取值的话，样本结果出现的概率}=\\frac{P(z_1 =A|y_1 ,θ^0)}  { P(z_1 =A|y_1 ,θ^0)+P(z_1 =B|y_1 ,θ^0) }=\\frac{0.6^5 ∗0.4^5}{0.6^5 ∗0.4^5 +0.5^{10}}  =0.45 $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "按照上面的计算方法可依次求出其他隐含变量$Z$，然后计算极大化的$θ^{(i)}$。\n",
    "\n",
    "经过10次迭代，最终收敛。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# K均值聚类和EM算法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "K均值聚类是无监督的聚类算法。\n",
    "\n",
    "关于k均值聚类不了解的可以参考：https://blog.csdn.net/luanpeng825485697/article/details/78993977"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "k均值聚类的目的就是为了使下面的损失函数最小"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$J(c,u)=\\sum_{i=1}^m||x_i-u_{c_i}||$$\n",
    "\n",
    "其中m为样本个数，$x_i$表示第$i$个样本，$c_i$表示第i个样本所属的聚类，$u_{c_i}$表示第i个样本所属的聚类的质心。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假设当前$J$没有达到最小值，那么首先可以固定每个类的质心$u_j$，调整每个样例的所属的类别$c_j$来让$J$函数减少，同样，固定$c_j$，调整每个类的质心$u_j$也可以使$J$减小。\n",
    "\n",
    "这两个过程就是内循环中使$J$单调递减的过程。当$J$递减到最小时，$u$和$c$也同时收敛。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**K-means与EM的关系**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "首先回到初始问题，我们目的是将样本分成K个类，其实说白了就是求一个样本的隐含类别y，然后利用隐含类别将x归类。\n",
    "\n",
    "由于我们事先不知道类别y，那么我们首先可以对每个样例假定一个y吧，但是怎么知道假定的对不对呢？怎样评价假定的好不好呢？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们使用样本的极大似然估计来度量，这里就是x和y的联合分布P（x,y）了。\n",
    "\n",
    "如果找到的y能够使P(x,y)最大，那么我们找到的y就是样例x的最佳类别了，x顺手就聚类了。\n",
    "\n",
    "但是我们第一次指定的y不一定会让P(x,y)最大，而且P(x,y)还依赖于其他未知参数，当然在给定y的情况下，我们可以调整其他参数让P(x,y)最大。\n",
    "\n",
    "但是调整完参数后，我们发现有更好的y可以指定，那么我们重新指定y，然后再计算P(x,y)最大时的参数，反复迭代直至没有更好的y可以指定。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**这个过程有几个难点：**\n",
    "\n",
    ">第一怎么假定y？是每个样例硬指派一个y还是不同的y有不同的概率，概率如何度量。（kmean中是硬指定，距离哪个聚类近就属于哪个聚类）\n",
    "\n",
    ">第二如何估计$P(x,y)$，$P(x,y)$还可能依赖很多其他参数，如何调整里面的参数让$P(x,y)$最大。（$J$函数最小来代替$P(x,y)$最大，我们可以将这些参数写成$θ$，更简单的理解$θ$就是k个质心的选择）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**按照EM算法思想:** E步就是估计隐含类别y的期望值，M步调整其他参数使得在给定类别y的情况下，极大似然估计$P(x,y)$能够达到极大值。然后在其他参数确定的情况下，重新估计y，周而复始，直至收敛。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "E步（E-step），以当前参数$θ$计算$Z$的期望值。也就是确定隐含类别变量$c$，样本所属的分类。我们固定每个类的中心，通过对每一个样本选择最近的分类，以此优化目标函数。\n",
    "\n",
    "M步（M-step），以当前$Z$的值计算使$P(x,y)$最大的$θ$。求使$J$函数最小的$u$，也就是求每个聚类的质心。重新更新每个类的中心点，该步骤可以通过对目标函数求导实现求解$θ$，最终可得新的类中心就是类中样本的均值。\n",
    "\n",
    "这里的隐含类别变量指定方法比较特殊，属于硬指定，从k个类别中硬选出一个给样例（距离哪个聚类近就属于哪个聚类），而不是对每个类别赋予不同的概率。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
